public class LeetCode198 {

    public static void main(String[] args) {
        int[] nums = {2, 7, 9, 3, 1};

        System.out.println(rob(nums));
    }

    public static int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        // 子问题：
        // f(k) = 偷 [0,k)房间中的最大金额

        // f(0) = 0
        // f(1) = nums[0]
        // f(k) = max(rob(k - 1), nums(k - 1) + rob (k - 2)

        int N = nums.length;
        int[] dp = new int[N + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i <= N; i++) {
            dp[i] = Math.max(dp[i - 1], nums[i - 1] + dp[i - 2]);
        }
        return dp[N];
    }

    public static int rob1(int[] nums) {
        int prev = 0;
        int curr = 0;

        // 每次循环，计算“偷到当前房子的最大金额”
        for (int i : nums) {
            // 循环开始时，curr 表示 dp[k - 1]，prev 表示 dp[k - 2]
            // dp[k] = max(dp[k - 1], dp[k - 2] + i)
            int temp = Math.max(curr, prev + i);
            prev = curr;
            curr = temp;
        }
        return curr;
    }
}
